// Scintilla source code edit control
/** @file Partitioning.h
 ** Data structure used to partition an interval. Used for holding line start/end positions.
 **/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.

#ifndef PARTITIONING_H
#define PARTITIONING_H

#include "Compat.h"

namespace Scintilla {

/// A split vector of integers with a method for adding a value to all elements
/// in a range.
/// Used by the Partitioning class.

template <typename T>
class SplitVectorWithRangeAdd : public SplitVector<T> {
 public:
  explicit SplitVectorWithRangeAdd(ptrdiff_t growSize_) {
    this->SetGrowSize(growSize_);
    this->ReAllocate(growSize_);
  }
  // Deleted so SplitVectorWithRangeAdd objects can not be copied.
  SplitVectorWithRangeAdd(const SplitVectorWithRangeAdd&) = delete;
  SplitVectorWithRangeAdd(SplitVectorWithRangeAdd&&) = delete;
  void operator=(const SplitVectorWithRangeAdd&) = delete;
  void operator=(SplitVectorWithRangeAdd&&) = delete;
  ~SplitVectorWithRangeAdd() {
  }
  void RangeAddDelta(ptrdiff_t start, ptrdiff_t end, T delta) noexcept {
    // end is 1 past end, so end-start is number of elements to change
    ptrdiff_t i = 0;
    const ptrdiff_t rangeLength = end - start;
    ptrdiff_t range1Length = rangeLength;
    const ptrdiff_t part1Left = this->part1Length - start;
    if (range1Length > part1Left) range1Length = part1Left;
    while (i < range1Length) {
      this->body[start++] += delta;
      i++;
    }
    start += this->gapLength;
    while (i < rangeLength) {
      this->body[start++] += delta;
      i++;
    }
  }
};

/// Divide an interval into multiple partitions.
/// Useful for breaking a document down into sections such as lines.
/// A 0 length interval has a single 0 length partition, numbered 0
/// If interval not 0 length then each partition non-zero length
/// When needed, positions after the interval are considered part of the last partition
/// but the end of the last partition can be found with PositionFromPartition(last+1).

template <typename T>
class Partitioning {
 private:
  // To avoid calculating all the partition positions whenever any text is inserted
  // there may be a step somewhere in the list.
  T stepPartition;
  T stepLength;
  std::unique_ptr<SplitVectorWithRangeAdd<T>> body;

  // Move step forward
  void ApplyStep(T partitionUpTo) noexcept {
    if (stepLength != 0) {
      body->RangeAddDelta(stepPartition + 1, partitionUpTo + 1, stepLength);
    }
    stepPartition = partitionUpTo;
    if (stepPartition >= body->Length() - 1) {
      stepPartition = Partitions();
      stepLength = 0;
    }
  }

  // Move step backward
  void BackStep(T partitionDownTo) noexcept {
    if (stepLength != 0) {
      body->RangeAddDelta(partitionDownTo + 1, stepPartition + 1, -stepLength);
    }
    stepPartition = partitionDownTo;
  }

  void Allocate(ptrdiff_t growSize) {
    body = Sci::make_unique<SplitVectorWithRangeAdd<T>>(growSize);
    stepPartition = 0;
    stepLength = 0;
    body->Insert(0, 0);  // This value stays 0 for ever
    body->Insert(1,
                 0);  // This is the end of the first partition and will be the start of the second
  }

 public:
  explicit Partitioning(int growSize) : stepPartition(0), stepLength(0) {
    Allocate(growSize);
  }

  // Deleted so Partitioning objects can not be copied.
  Partitioning(const Partitioning&) = delete;
  Partitioning(Partitioning&&) = delete;
  void operator=(const Partitioning&) = delete;
  void operator=(Partitioning&&) = delete;

  ~Partitioning() {
  }

  T Partitions() const noexcept {
    return static_cast<T>(body->Length()) - 1;
  }

  T Length() const noexcept {
    return PositionFromPartition(Partitions());
  }

  void InsertPartition(T partition, T pos) {
    if (stepPartition < partition) {
      ApplyStep(partition);
    }
    body->Insert(partition, pos);
    stepPartition++;
  }

  void SetPartitionStartPosition(T partition, T pos) noexcept {
    ApplyStep(partition + 1);
    if ((partition < 0) || (partition > body->Length())) {
      return;
    }
    body->SetValueAt(partition, pos);
  }

  void InsertText(T partitionInsert, T delta) noexcept {
    // Point all the partitions after the insertion point further along in the buffer
    if (stepLength != 0) {
      if (partitionInsert >= stepPartition) {
        // Fill in up to the new insertion point
        ApplyStep(partitionInsert);
        stepLength += delta;
      } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
        // Close to step but before so move step back
        BackStep(partitionInsert);
        stepLength += delta;
      } else {
        ApplyStep(Partitions());
        stepPartition = partitionInsert;
        stepLength = delta;
      }
    } else {
      stepPartition = partitionInsert;
      stepLength = delta;
    }
  }

  void RemovePartition(T partition) {
    if (partition > stepPartition) {
      ApplyStep(partition);
      stepPartition--;
    } else {
      stepPartition--;
    }
    body->Delete(partition);
  }

  T PositionFromPartition(T partition) const noexcept {
    PLATFORM_ASSERT(partition >= 0);
    PLATFORM_ASSERT(partition < body->Length());
    const ptrdiff_t lengthBody = body->Length();
    if ((partition < 0) || (partition >= lengthBody)) {
      return 0;
    }
    T pos = body->ValueAt(partition);
    if (partition > stepPartition) pos += stepLength;
    return pos;
  }

  /// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
  T PartitionFromPosition(T pos) const noexcept {
    if (body->Length() <= 1) return 0;
    if (pos >= (PositionFromPartition(Partitions()))) return Partitions() - 1;
    T lower = 0;
    T upper = Partitions();
    do {
      const T middle = (upper + lower + 1) / 2;  // Round high
      T posMiddle = body->ValueAt(middle);
      if (middle > stepPartition) posMiddle += stepLength;
      if (pos < posMiddle) {
        upper = middle - 1;
      } else {
        lower = middle;
      }
    } while (lower < upper);
    return lower;
  }

  void DeleteAll() {
    Allocate(body->GetGrowSize());
  }

  void Check() const {
#ifdef CHECK_CORRECTNESS
    if (Length() < 0) {
      throw std::runtime_error("Partitioning: Length can not be negative.");
    }
    if (Partitions() < 1) {
      throw std::runtime_error("Partitioning: Must always have 1 or more partitions.");
    }
    if (Length() == 0) {
      if ((PositionFromPartition(0) != 0) || (PositionFromPartition(1) != 0)) {
        throw std::runtime_error("Partitioning: Invalid empty partitioning.");
      }
    } else {
      // Positions should be a strictly ascending sequence
      for (T i = 0; i < Partitions(); i++) {
        const T pos = PositionFromPartition(i);
        const T posNext = PositionFromPartition(i + 1);
        if (pos > posNext) {
          throw std::runtime_error("Partitioning: Negative partition.");
        } else if (pos == posNext) {
          throw std::runtime_error("Partitioning: Empty partition.");
        }
      }
    }
#endif
  }
};

}  // namespace Scintilla

#endif
